\documentclass{beamer}
\usepackage[utf8]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Creating a \commonlisp{} implementation\\(Part 2)}

\author{Robert Strandh}
\institute{
}
\date{June, 2020}

%\inputtex{macros.tex}

\begin{document}
\frame{
\titlepage
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Topics covered in presentation series}
\vskip 0.25cm
\begin{itemize}
\item Choices of implementation language.
\item Implementation strategies for the evaluator.
\item Division of code written in \commonlisp{} and code written in
  the implementation language.
\end{itemize}
}

\frame{
\frametitle{Topics not covered in presentation series}
\vskip 0.25cm
\begin{itemize}
\item How a \commonlisp{} compiler works.  If there is a demand, maybe
  in a different series.
\item How different strategies for memory management work.
\item Details about how an abstract machine could work.
\item Details about how a typical concrete processor works.
\end{itemize}
}

\frame{
\frametitle{Recapitulation, strategy 1}
\vskip 0.25cm
\begin{itemize}
\item A \emph{core} written in an existing language, typically C.
\item Additional modules written in \commonlisp{} added to the core.
\end{itemize}
}

\frame{
\frametitle{Why C?}
\vskip 0.25cm
There was a question during the streaming of part 1, namely ``Why use
C rather than C++?''
\vskip 0.25cm
Answer: The purpose of the presentations is not to choose an optimal
language for strategy 1, but to show the complications of strategy 1,
no matter the language chosen, namely:
\vskip 0.25cm
\begin{itemize}
\item The imposed order between modules makes it necessary to write
  more code in the language of the core.
\item And it makes the the \commonlisp{} code of each additional
  module look ``unnatural'' because we are forced to use a subset of
  \commonlisp{}.
\end{itemize}
}

\frame{
\frametitle{Recapitulation, strategy 1}
\vskip 0.25cm
The core may contain more than what we would have liked:
\vskip 0.25cm
\begin{itemize}
\item An \emph{inner core}:
  \begin{itemize}
  \item Object allocation.
  \item Memory management.
  \item Accessors for built-in object types.
  \end{itemize}
\item An \emph{extended core}:
  \begin{itemize}
  \item Functions placed here in order to break circular
    dependencies.
  \item Temporary or permanent functions required for bootstrapping,
    like \texttt{read} and \texttt{eval}.
  \end{itemize}
\end{itemize}
}

\frame{
\frametitle{Recapitulation, strategy 1}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-recapitulation-strategy-1.pdf_t}
\end{center}
\end{figure}
}

\frame[containsverbatim]{
\frametitle{Recapitulation, strategy 1}
\vskip 0.25cm
The inner core may contain functions at a level lower than the lowest
level of \commonlisp{}.  Example:
\begin{verbatim}
(defun car (object)
  (if (consp object)
      (core:cons-car object)
      (if (null object)
          nil
          (error ...))))
\end{verbatim}
\vskip 0.25cm
Here, \texttt{car} is part of the \commonlisp{} code, and
\texttt{cons-car} is part of the inner core.
}

\frame{
\frametitle{Strategy 1: Evaluator}
\vskip 0.25cm
Recall that we have the following choices:
\begin{enumerate}
\item A direct interpreter.
\item A compiler generating bytcodes plus a bytecode interpreter.
\item A compiler generating native code.
\end{enumerate}
\vskip 0.25cm
Our current choice is for option 2.
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-stack.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-1.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-2.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-3.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-4.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-5.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-6.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-7.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-8.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-9.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-10.pdf_t}
\end{center}
\end{figure}
}


\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-11.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-12.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-13.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-14.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-15.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-16.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Call stack}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-call-17.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Dynamic environment}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-dynamic-environment.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Static environment}
\vskip 0.25cm
A function object consists of:
\begin{itemize}
\item An \emph{entry point} which is the address of the
  first instruction of the function.
\item A \emph{static environment} which contains closed-over
  variables and perhaps complicated constants.
\end{itemize}
\vskip 0.25cm
The entry point can be shared with other functions.
}

\frame[containsverbatim]{
\frametitle{Static environment}
\vskip 0.25cm
Example:
\vskip 0.25cm
\begin{verbatim}
(defun foo (x)
  (lambda (y) (+ x y)))

(list (foo 1) (foo 2))
\end{verbatim}
}


\frame{
\frametitle{Static environment}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-static-environment.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Implicit arguments to a function}
\vskip 0.25cm
\begin{itemize}
\item The return address.
\item The static environment.
\item The dynamic environment.
\end{itemize}
}

\frame{
\frametitle{Abstract machine}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-abstract-machine-1.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Abstract machine}
\vskip 0.25cm
The instructions of the machine correspond to the functionality of the
core, namely:
\begin{itemize}
\item Allocators for built-in types.
\item Predicates for those types.
\item Slot accessors for those types.
\item Fixnum and floating-point arithmetic.
\end{itemize}
\vskip 0.25cm
Floating-point arithmetic is in the core for reasons of performance.
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-1.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-2.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-3.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-4.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-5.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-6.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-7.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-8.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Function call}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-function-call-9.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{More about complications}
\vskip 0.25cm
Recall from part 1 that:
\vskip 0.25cm
\begin{itemize}
\item The \texttt{mapcar} function needs the \texttt{do} macro when it
  is compiled.
\item The \texttt{do} macro function needs the \texttt{mapcar}
  function when it is executed.
\end{itemize}
\vskip 0.25cm
Let us formalize this dependency a bit.
}

\frame{
\frametitle{Dependencies, execution}
\vskip 0.25cm
This relation means that the \emph{execution} of A may
invoke B.
\begin{figure}
\begin{center}
\inputfig{fig-dependencies-1.pdf_t}
\end{center}
\end{figure}
\vskip 0.25cm
Executing a macro means executing the macro function, which is usually
done by the compiler at compile time.
}

\frame[containsverbatim]{
\frametitle{Dependencies, example}
\vskip 0.25cm
{\small\begin{verbatim}
(defun cadr (object)
  (car (cdr object)))
\end{verbatim}
\begin{figure}
\begin{center}
\inputfig{fig-dependencies-4.pdf_t}
\end{center}
\end{figure}
}
}

\frame[containsverbatim]{
\frametitle{Dependencies, example}
\vskip 0.25cm
{\small\begin{verbatim}
(defmacro case (expression &rest clauses)
  (let ((expression-var (gensym)))
    `(let ((,expression-var ,expression))
       (cond ,@(mapcar (lambda (clause)
                         `((eql ,expression-var
                                ',(first clause))
                           ,@(rest clause)))
                       clauses)))))
\end{verbatim}
\begin{figure}
\begin{center}
\inputfig{fig-dependencies-3.pdf_t}
\end{center}
\end{figure}
}
}

\frame{
\frametitle{Dependencies, compilation}
\vskip 0.25cm
This relation means that the \emph{compilation} of A may
invoke B.
\begin{figure}
\begin{center}
\inputfig{fig-dependencies-2.pdf_t}
\end{center}
\end{figure}
}

\frame[containsverbatim]{
\frametitle{Dependencies, example}
\vskip 0.25cm
{\small\begin{verbatim}
(defmacro prog (bindings &body body)
  (multiple-value-bind (declarations items)
      (separate-ordinary-body body)
    `(block nil
       (let ,bindings
         ,@declarations
         (tagbody ,@items)))))
\end{verbatim}
\begin{figure}
\begin{center}
\inputfig{fig-dependencies-5.pdf_t}
\end{center}
\end{figure}
}
}

\frame[containsverbatim]{
\frametitle{Dependencies, example}
\vskip 0.25cm
{\small\begin{verbatim}
(defun mapcar (function list)
  (do ((sublist list (rest sublist))
       (result '()))
      ((null sublist) (nreverse result))
    (push (funcall function (first sublist))
          result)))
\end{verbatim}
\begin{figure}
\begin{center}
\inputfig{fig-dependencies-6.pdf_t}
\end{center}
\end{figure}
}
}

\frame[containsverbatim]{
\frametitle{Dependencies, normal recursion}
\vskip 0.25cm
A circular dependency with only black arrows represents
ordinary recursion.  No compile-time dependency.
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-normal-recursion.pdf_t}
\end{center}
\end{figure}
}

\frame[containsverbatim]{
\frametitle{Dependencies, compile time}
\vskip 0.25cm
A circular dependency with at least one red arrow represents
compile-time self-dependency, and must be eliminated.
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-compile-time-dependency.pdf_t}
\end{center}
\end{figure}
}

\frame[containsverbatim]{
\frametitle{Example from part 1}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-example-from-part-1.pdf_t}
\end{center}
\end{figure}
}

\frame[containsverbatim]{
\frametitle{Example from part 1}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-full-example-from-part-1.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Topics for part 3}
\vskip 0.25cm
In part 3:
\vskip 0.25cm
\begin{itemize}
\item We resolve the dependency problem by cross-compiling code on a
  host \commonlisp{} implementation. 
\item The cross compiler will generate bytecodes for the abstract
  machine.
\item The core is still written in C, and it contains the bytecode
  loader and the bytecode interpreter.
\item But we can now move much of the C code to \commonlisp{}
\end{itemize}
\vskip 0.25cm
This summarizes our strategy 2 which is the main topic of part 3.
}

\end{document}
